Міністерство освіти та науки України Національний університет "Львівська політехніка" Кафедра ЕОМ / Курсова робота з дисципліни "Паралельні та розподілені обчислення" на тему "Паралельне виконання операцій множення матриць" Варіант №16  Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністюn1*n2) на матрицю В (розмірністюn2*n3) на заданій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці. Для визначення варіанту були виконані наступні дії: визначення розмірів матриць (декодування літер згідно номеру групи): n1=2П,n2=2Б,n3=1І– КІ-43 Таблиця 1. Порядкові номери літер прізвища, імені та по-батькові 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  Р О М А Н О В С Ь К И Й О Л Е К  17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  С А Н Д Р В І Т А Л І Й О В И Ч  n1 = О n2 = І n3 = О Згідно таблиці декодування літер маємо: N1 = 240 N2 = 176 N3 = 333 Отже, отримаємо такі матриці: А (240*176) В (176*333) С (240*333) для визначення типу пам’яті використовуємо формулу:
(25 mod 3) + 1 = 2 –>завантаження даних через 1 процесор; для знаходження часових співвідношень використовуємо наступну формулу: tU=(Zk-3 +1)*tS=(Zk-2 +1)*tP=(Zk-1 +1)*tZ=(Zk+1)*tW tU = 10tS  = 6tP =8tZ = 4tW Результати декодування літер ПІБ, визначення типу пам’яті та знаходженні часових співвідношень у таблиці 2. Таблиця 2 № вар Розміри матриці К-ть процесорів Тип початкового завантаження даних Співвідношення часових параметрів   N1 N2 N3     16 240 176 333 8 2 tU = 10tS  = 6tP =8tZ = 4tW   Примітка: 2*- завантаження початкових даних в процесори через один з них; tU – час виконання однієї операції множення; tS  - час виконання однієї операції сумування; tP - час виконання однієї операції пересилання даних між процесорами; tZ - час виконання операції завантаження одних даних; tW - час виконання операції вивантаження одних даних. для того, щоб розробити та описати алгоритм множення матриць А*В на структурі, яка задається використовуємо наступний вираз: 14b-8b-1b-3b-9b-2b-11b-5b – КІ-43, де «nb»- номер букви П.І.Б студента 1 2 3 4 5 6 7 8 9  10 11  12  13  14  15 16  17  18 19  20 21  Р О М А Н О В С Ь  К И  Й  О  Л  Е К С А Н  Д Р  3 6 4  8   2 5  7    1          Згідно таблиці кодування букв отримали такий варіант-стовпець: ЛСРМЬОИН Л – 21210= 1 1 0 1 0 1 0 02 С – 8210=0 1 0 1 0 0 1 02 Р – 9310= 0 1 0 1 1 1 0 12 М – 4310= 0 0 1 0 1 0 1 12 Ь – 2810=0 0 0 1 1 1 0 02 О – 25010= 1 1 1 1 1 0 1 02 И – 9110= 0 1 0 1 1 0 1 12 Н – 13410= 1 0 0 0 0 1 1 02 В отриманій двійковій матриці одиниці, що розташовані по головній діагоналі замінюємо на 0. 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 ( 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0Анотація В даній курсовій роботі розроблена структура перемноження матриці на матриц, яка складається з 8-ми процесорів; завантаження початкових даних в процесори відбувається через один з них. Розміри матриць задані згідно із варіантом. Також пораховано час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з варіанту. В курсовій роботі розроблено граф-схему виконання алгоритму множення двох матриць, граф-схему загальної схеми виконання програми та граф-схему покрокового виконання алгоритму. Програмне забезпечення до курсової роботи виконане у середовищі Microsoft Visual Studio 2010 на мові С++ з використанням бібліотек MPI. Програмне забезпечення до курсової роботи має консольний інтерфейс.  Annotation In this course work was developed the structure of the matrix to matrix multiplica...